﻿#include "dsatur.h"

vector<int> coloresAdy;

struct dsatur_orden
{
    bool operator()(Nodo *a, Nodo *b){
        // Ordenar primero por orden de saturación decreciente. Si los órdenes de 
        // saturación coinciden, se usa el nodo con el grado más alto. Nótese que
        // el caso inicial está cubierto ya que todos los nodos tienen saturación
        // cero y estarán naturalmente ordenados por grado decrecientemente.
        if (a->getSaturacion() == b->getSaturacion()) {
            if (a->grado == b->grado) {
                return a->getId() < b->getId();
            } else {
                return a->grado > b->grado;
            }
        } else {
            return a->getSaturacion() > b->getSaturacion();
        }
    }
} dsatur_orden_inst;

int d1 = 0;

void dsaturReordenarSinColor(set<Nodo*, dsatur_orden> *sin_color, const vector<Nodo*> ady){

    vector<Nodo*> reordenar;

    int d2 = 0;
    // Actualizar la saturación de cada nodo adyacente no coloreado
    for (vector<Nodo*>::const_iterator itAdy = ady.begin(); itAdy != ady.end(); ++ itAdy){

        ++ d2;
        // El número de saturación sólo es importante para determinar el orden de los
        // nodos no coloreados
        if (!binary_search(sin_color->begin(), sin_color->end(), *itAdy, dsatur_orden_inst)){
            continue;
        }

        vector<Nodo*> vecinos = (*itAdy)->getAdyacentes();

        // Ahora que el nodo actual tiene un nuevo color, la saturación de cada adyacente
        // puede variar. Para esto se revisa cada vecino del adyacente
        for (vector<Nodo*>::iterator itAdyAdy = vecinos.begin(); itAdyAdy != vecinos.end(); ++ itAdyAdy){

            vector<int>::iterator itCol;
            // Crear un vector con todos los colores distintos alrededor de este nodo adyacente
            for (itCol = coloresAdy.begin(); itCol != coloresAdy.end(); ++ itCol){
                if (*itCol == (*itAdyAdy)->getColor()){
                    break;
                }
            }
            // Color nuevo detectado entre los vecinos del adyacente
            if (itCol == coloresAdy.end()){
                coloresAdy.push_back((*itAdyAdy)->getColor());
            }
        }

        // Cambió la saturación, al terminar de revisar las saturaciones,
        // indicar que hay que reordenar el elemento
        if (coloresAdy.size() != (*itAdy)->getSaturacion()){

            set<Nodo*, dsatur_orden>::iterator ita = lower_bound(sin_color->begin(), sin_color->end(), *itAdy, dsatur_orden_inst);
            // Como es un árbol ordenado, al volver a insertarlo, se colocará en la posición correcta
            Nodo *t = *ita;
            sin_color->erase(ita);
            t->setSaturacion(coloresAdy.size());
            sin_color->insert(t);
        }
    }
}

void dsatur(Grafo *grafo, vector<int>* order){
    set<Nodo*, dsatur_orden> sin_color;
    bool *colores = new bool[grafo->getTam() + 1];

    // Inicialmente ningún nodo tiene color
    for (int i = 1; i <= grafo->getTam(); ++ i){
        grafo->getNodo(i)->setColor(0);
        sin_color.insert(grafo->getNodo(i));
    }

    // Colores alrededor de cada adyacente, sabemos que nunca van a ser más que el tamaño del grafo
    coloresAdy.reserve(grafo->getTam());

    while (0 != sin_color.size()){

        set<Nodo*, dsatur_orden>::iterator it = sin_color.begin();
        Nodo *actual = *it;
        sin_color.erase(it);

        vector<Nodo*> ady = actual->getAdyacentes();

        // Inicialmente todos los colores están disponibles para este nodo
        memset(colores, 0, (grafo->getTam() + 1) * sizeof(bool));

        // Marcar los colores utilizados por los nodos adyacentes
        for (vector<Nodo*>::iterator itAdy = ady.begin(); itAdy != ady.end(); ++ itAdy){
            colores[(*itAdy)->getColor()] = true;
        }

        // Encontrar el color de numeración más baja no usado por los nodos adyacentes
        // Nótese que en el caso incial, el nodo de más alto grado tendrá el color 1
        int c = 1;
        while (c <= grafo->getTam() && colores[c]) ++ c;
        if (grafo->getTam() + 1 == c){
            printf("error interno, no hay color posible para el nodo");
            exit(1);
        }
        actual->setColor(c);

        if (0 != order) {
            order->push_back(actual->getId());
        }

        dsaturReordenarSinColor(&sin_color, ady);
    }
    
    delete[] colores;
}